/**
 * 
 */
package uk.ac.manchester.cs.util;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

/**
 * Implements an iterator over the cross product of sets
 * 
 * Adapted from a version by Jacek Kolodziejczyk (jacek.p.kolodziejczyk@gmail.com) 
 * 
 * @author Pavel Klinov
 *
 */
public class CrossProductIterator<T> implements Iterator<Set<T>> {
	
	private List<Iterable<T>> m_iterables = null;
	private List<Iterator<T>> m_iterators = null; 
	private boolean m_empty = false;
	private List<T> m_next = null;
	
	public CrossProductIterator(Collection<? extends Iterable<T>> iterables) {
		
		int size = iterables.size();
		m_iterables = new ArrayList<Iterable<T>>(size);
		m_iterators = new ArrayList<Iterator<T>>(size);
		m_next = new ArrayList<T>(size);
		
		for (Iterable<T> iterable : iterables) {
			
			Iterator<T> iterator = iterable.iterator();
			
			if (!iterator.hasNext()) {
				
				m_empty = true;
				break;
				
			} else {
				
				m_iterables.add(iterable);
				m_iterators.add(iterable.iterator());				
			}
		}
		

		if (!m_empty) {
			
			for (int i = 0; i < size-1; i++) {
				
				m_next.add(m_iterators.get(i).next());
			}
			
			m_next.add(null);
		}
	}

	@Override
	public boolean hasNext() {
		
		if (m_empty) return false;
		
		for (Iterator<T> iterator : m_iterators) {
			
			if (iterator.hasNext()) return true;
		}
		
		return false;
	}

	@Override
	public Set<T> next() {
		// Find first in reverse order iterator the has a next element
		int cursor = 0;
		int size = m_iterables.size();
		
		for (cursor = size-1; cursor >= 0; cursor--) {
			
			if (m_iterators.get(cursor).hasNext()) break;
		}

		// Initialize iterators next from the current one  
		for (int i = cursor+1; i < size; i++) {
			
			m_iterators.set(i, m_iterables.get(i).iterator());
		}
		
		// Get the next value from the current iterator and all the next ones  
		for (int i = cursor; i < size; i++) setNextValue(i);

		return new HashSet<T>(m_next);
	}
	
	private void setNextValue(int index) {
		
		Iterator<T> iterator = m_iterators.get(index);
		
		if (iterator.hasNext()) {
		
			m_next.set(index, iterator.next());
		}
	}

	@Override
	public void remove() {

		throw new UnsupportedOperationException();
	}

}
